//
//  402. 移掉K位数字.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/9/12.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution402 {
    // 实际上维持一个单调栈就可以了
    func removeKdigits(_ num: String, _ k: Int) -> String {
        var stack: [Character] = []
        var m = k
      
        for item in num {
            // 维持单调栈的精髓
            while !stack.isEmpty && item < stack.last! && m > 0 {
                stack.removeLast()
                m -= 1
            }
            // 栈不为nil 或者 item 不为"0"
            if !stack.isEmpty || item != "0" {
                stack.append(item)
            }
        }
        // 还没有删够
        while !stack.isEmpty &&  m > 0 {
            stack.removeLast()
            m -= 1
        }
        // 栈为nil
        if stack.isEmpty  {
            return "0"
        }
        return String(stack)
    }
    static func test() {
        let solution = Solution402()
        let num = "10"
        let k = 2
        let result = solution.removeKdigits(num, k)
        print(result)
    }
}
